package com.blah.gwtgames.client.sudoku;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

import com.blah.gwtgames.client.common.dlx.Choice;
import com.blah.gwtgames.client.common.dlx.Constraint;
import com.blah.gwtgames.client.common.dlx.DancingLinks;
import com.blah.gwtgames.client.common.dlx.SolvedCallback;

public class SudokuSolver
{
	private DancingLinks matrix = new DancingLinks();
	private Map constraints = new HashMap();
	private Sudoku sudoku;
	private int dimension;
	
	public SudokuSolver(int dimension)
	{
		this.dimension = dimension;
		
		// Create the matrix
		makeConstraints();
		makeChoices();
	}
	
	public SudokuSolver(Sudoku sudoku)
	{
		this(sudoku.getDimension());
		
		setPuzzle(sudoku);
	}
	
	public void setPuzzle(Sudoku sudoku)
	{
		if (sudoku.getDimension() != dimension)
			throw new IllegalArgumentException(
					"This solver is for " + dimension + "x" + dimension + " puzzles. " +
					"This puzzle is " + sudoku.getDimension() + "x" + sudoku.getDimension() + ".");
			
		while (matrix.canUndo())
		{
			matrix.undo();
		}
		
		this.sudoku = sudoku;
		
		for (int x = 0; x < dimension; ++x)
		{
			for (int y = 0; y < dimension; ++y)
			{
				if (sudoku.isLocked(x, y))
				{
					matrix.choose(getChoiceKey(x, y, sudoku.getValue(x, y)));
				}
			}
		}	}
	
	public void solve()
	{
		matrix.solve(new SolvedCallback()
		{
			public void solved(Set choices)
			{
				Iterator iterator = choices.iterator();
				while (iterator.hasNext())
				{
					SudokuChoice choice = (SudokuChoice)iterator.next();
					sudoku.setValue(choice.getRow(), choice.getColumn(), choice.getValue());
				}
				
				matrix.halt();
			}	
		});
		
		
	}

	private void makeConstraints()
	{
		for (int value = 1; value <= dimension; ++value)
		{
			for (int row = 0; row < dimension; ++row)
			{
				addConstraint(getRowConstraintName(row, value));
			}
			
			for (int column = 0; column < dimension; ++column)
			{
				addConstraint(getColumnConstraintName(column, value));
			}
			
			for (int i = 0; i < dimension; ++i)
			{
				addConstraint(getBlockConstraintName(i / 3, i % 3, value));
			}
		}
		
		for (int row = 0; row < dimension; ++row)
		{
			for (int column = 0; column < 9; ++column)
			{
				addConstraint(getCellConstraintName(row, column));
			}
		}
	}
	
	private void makeChoices()
	{
		for (int value = 1; value <= dimension; ++value)
		{
			for (int row = 0; row < dimension; ++row)
			{
				for (int column = 0; column < dimension; ++column)
				{
					Choice choice = new SudokuChoice(row, column, value);
					choice.addConstraint(
							(Constraint)constraints.get(getCellConstraintName(row, column)));
					choice.addConstraint(
							(Constraint)constraints.get(getRowConstraintName(row, value)));
					choice.addConstraint(
							(Constraint)constraints.get(getColumnConstraintName(column, value)));
					choice.addConstraint(
							(Constraint)constraints.get(getBlockConstraintName(row / 3, column / 3, value)));
					
					matrix.addChoice(choice);
				}
			}
		}
	}

	private void addConstraint(String name)
	{
		Constraint constraint = new Constraint();
		constraints.put(name, constraint);
		matrix.addConstraint(constraint);
	}

	private String getCellConstraintName(int row, int column)
	{
		return "R" + row + "C" + column;
	}
	
	private String getColumnConstraintName(int column, int value)
	{
		return "C" + column + "#" + value;
	}
	
	private String getRowConstraintName(int row, int value)
	{
		return "R" + row + "#" + value;
	}
	
	private String getBlockConstraintName(int x, int y, int value)
	{
		return "X" + x + "Y" + y + "#" + value;
	}
	
	private Object getChoiceKey(int row, int column, int value)
	{
		return new Integer(
				row * dimension * dimension +
				column * dimension +
				value);
	}
	
	private class SudokuChoice extends Choice
	{
	    private int row;
		private int column;
		private int value;
		
		SudokuChoice(int row, int column, int value)
		{
			this.row = row;
			this.column = column;
			this.value = value;
			
			setKey(getChoiceKey(row,column,value));
		}
		
		int getRow() {return row;}
		int getColumn() {return column;}
		int getValue() {return value;}
	}
}
